package com.example.demo.algorithm.tree;

import com.example.demo.algorithm.linear.Queue;

/**
 * @Author: xiatian
 * @CreateTime: 2022/1/10 7:25 下午
 * @Description:
 */
public class BinaryTree<Key extends Comparable<Key>, Value> {
    //记录根节点
    private Node root;
    //记录树中元素的个数
    private int N;

    //向树中插入一个键值对
    public void put(Key key, Value value) {
        root = put(this.root, key, value);
    }

    //给指定树x上，添加键一个键值对，并返回添加后的新树
    private Node put(Node x, Key key, Value val) {
        //x子树为空
        if (x == null) {
            N++;
            return new Node(key, val, null, null);
        }
        //比较x节点的键和key的大小
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            //如果key大于x节点的键，则继续找x节点的右子树
            x.right = put(x.right, key, val);
        } else if (cmp < 0) {
            //如果key小于x节点的键，则继续找x节点的左子树
            x.left = put(x.left, key, val);
        } else if (cmp == 0) {
            //如果key等于x节点的键则替换掉值
            x.value = val;
        }
        return x;
    }

    //根据key，从树中找出对应的值
    public Value get(Key key) {
        return get(root, key);
    }

    //从指定的树x中，找出key对应的值
    private Value get(Node x, Key key) {
        //x子树为空
        if (x == null) {
            return null;
        }
        //比较x节点的键和key的大小
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            //如果key大于x节点的键，则继续找x节点的右子树
            return get(x.right, key);
        } else if (cmp < 0) {
            //如果key小于x节点的键，则继续找x节点的左子树
            return get(x.left, key);
        } else {
            //如果key等于x节点的键则返回值
            return x.value;
        }

    }

    //根据key，删除树中对应的键值对
    public void delete(Key key) {
        delete(root, key);
    }

    //删除指定树x上的键为key的键值对，并返回删除后的新树
    private Node delete(Node x, Key key) {
        //x子树为空
        if (x == null) {
            return null;
        }
        //比较x节点的键和key的大小
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            //如果key大于x节点的键，则继续找x节点的右子树
            x.right = delete(x.right, key);
        } else if (cmp < 0) {
            //如果key小于x节点的键，则继续找x节点的左子树
            x.left = delete(x.left, key);
        } else if (cmp == 0) {
            //如果key等于x节点的键则完成删除的动作，要删除的节点就是x
            N--;
            if (x.right == null) {
                return x.left;
            }
            if (x.left == null) {
                return x.right;
            }
            //寻找右子树中最小的节点
            Node minNode = x.right;
            while (minNode.left != null) {
                minNode = minNode.left;
            }
            //删除右子树中最小的节点
            Node n = x.right;
            while (n.left != null) {
                //如果左子节点的下一个左子节点为空
                if (n.left.left == null) {
                    n.left = null;
                } else {
                    n = n.left;
                }
            }
            //让x节点的左子树成为minNode的左子树
            minNode.left = x.left;
            //让x节点的右子树成为minNode的右子树
            minNode.right = x.right;
            //让x节点的父节点指向minNode
            x = minNode;
        }
        return x;
    }

    //获取树中元素的个数
    public int size() {
        return N;
    }

    //查找整个树种最小的键
    public Key min() {
        return min(root);
    }

    //查找整个树种最小的键
    public Key min(Node x) {
        while (x.left != null) {
            x = x.left;
        }
        return x.key;
    }

    //查找整个树种最大的键
    public Key max() {
        return max(root).key;
    }

    //查找整个树种最大的键
    public Node max(Node x) {
        while (x.right != null) {
            return max(x.right);
        }
        return x;
    }

    //使用前序遍历，获取整个树种的所有键
    public Queue<Key> preErgodic() {
        Queue<Key> keys = new Queue<>();
        preErgodic(root, keys);
        return keys;
    }

    //获取指定树x的所有键，并放到keys队列中
    public void preErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }
        //把x节点的key放在keys中
        keys.enqueue(x.key);
        //递归遍历x节点的左子树
        if (x.left != null) {
            preErgodic(x.left, keys);
        }
        //递归遍历x节点的右子树
        if (x.right != null) {
            preErgodic(x.right, keys);
        }
    }

    //使用中序遍历，获取整个树种的所有键
    public Queue<Key> midErgodic() {
        Queue<Key> keys = new Queue<>();
        midErgodic(root, keys);
        return keys;
    }

    //获取指定树x的所有键，并放到keys队列中
    public void midErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }
        //递归遍历x节点的左子树
        if (x.left != null) {
            midErgodic(x.left, keys);
        }
        //把x节点的key放在keys中
        keys.enqueue(x.key);
        //递归遍历x节点的右子树
        if (x.right != null) {
            midErgodic(x.right, keys);
        }
    }

    //使用后序遍历，获取整个树种的所有键
    public Queue<Key> afterErgodic() {
        Queue<Key> keys = new Queue<>();
        afterErgodic(root, keys);
        return keys;
    }

    //获取指定树x的所有键，并放到keys队列中
    public void afterErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }
        //递归遍历x节点的左子树
        if (x.left != null) {
            afterErgodic(x.left, keys);
        }
        //递归遍历x节点的右子树
        if (x.right != null) {
            afterErgodic(x.right, keys);
        }
        //把x节点的key放在keys中
        keys.enqueue(x.key);
    }

    //使用层序遍历，获取整个树中所有的键
    public Queue<Key> layerErgodic() {
        //定义两个队列，分别存储树的键和树的节点
        Queue<Node> nodes = new Queue<>();
        Queue<Key> keys = new Queue<>();
        //默认往队列中放入根节点
        nodes.enqueue(root);
        while (!nodes.isEmpty()) {
            //从队列中弹出一个节点，把key放入nodes中
            Node n = nodes.dequeue();
            keys.enqueue(n.key);
            //判断当前节点还有没有左子节点，如果有就放入nodes中
            if (n.left != null) {
                nodes.enqueue(n.left);
            }
            //判断当前节点还有没有右子节点，如果有就放入nodes中
            if (n.right != null) {
                nodes.enqueue(n.right);
            }
        }
        return keys;
    }

    //计算整个树的最大深度
    public int maxDepth() {
        return maxDepth(root);
    }

    public int maxDepth(Node x) {
        if (x == null) {
            return 0;
        }
        int maxDepth = 0;
        int maxL = 0;
        int maxR = 0;
        //计算左子树的最大深度
        if (x.left != null) {
            maxL = maxDepth(x.left);
        }
        //计算右子树的最大深度
        if (x.right != null) {
            maxR = maxDepth(x.right);
        }
        //当前
        maxDepth = maxL > maxR ? maxL + 1 : maxR + 1;
        return maxDepth;
    }


    public class Node {
        private Key key;
        public Value value;
        private Node left;
        private Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}
